package _08_动态规划;
/*
    动态规划:1.找零钱
 */
public class CoinChange {
    public static void main(String[] args) {
        System.out.println(coins(19));
        System.out.println(coins2(19));
        System.out.println(coins3(19));
    }


    //通用实现,可以传面值数组
    static int coins4(int n,int[] faces){
        if(n<1 || faces == null || faces.length == 0) return 0;
        int[] dp = new int[n+1]; //结果数组
        for(int i=1;i<=n;++i){
            int min = Integer.MAX_VALUE;
            for (int face : faces) {
                if(i<face) continue; //当前需要凑的钱数小于面值
                if(dp[i-face]<0 || dp[i-face]>=min) continue;//凑够i分已经够了，就不需要在凑了
                min = dp[i-face];
            }
            //最小值的不合法情况
            if(min == Integer.MAX_VALUE){
                dp[i] = -1;
            }else{ //面值加1
                dp[i] = min + 1;
            }
        }
        return dp[n];
    }

    //递推(自底向上)，由于经过前两次发现，找到n分所需的硬币个数都是由先算出子问题的解，才能推算出n
    //所以我们可以先计算出子问题，向上推，直到推出大问题
    static int coins3(int n){
        if(n<1) return Integer.MAX_VALUE;
        int[] dp = new int[n+1]; //存放结果数组，第0个不用，从1-n
        int[] faces = new int[dp.length]; //faces[i]是凑够i分时最后那枚硬币的面值
        for(int i=1;i<=n;++i){ //从1到n递推出每一种需要的硬币个数
            //dp[i] = min{dp[i-25],dp[i-20],dp[i-5],dp[i-1]}+1;
            int min = Integer.MAX_VALUE;
            if(i>=1 && dp[i-1] <= min){
                min = dp[i-1];
                faces[i] = 1; //凑够i分时的那枚硬币
            }
            if(i>=5 && dp[i-5] <= min){
                min = dp[i-5];
                faces[i] = 5; //凑够i分时的那枚硬币
            }
            if(i>=20 && dp[i-20] <= min){
                min = dp[i-20];
                faces[i] = 20; //凑够i分时的那枚硬币
            }
            if(i>=25 && dp[i-25] <= min){
                min = dp[i-25];
                faces[i] = 25; //凑够i分时的那枚硬币
            }
            dp[i] = min + 1; //上述已经选了一次，所以硬币数加1
        }
        print(faces,n);
        return dp[n]; //返回最终需要的结果
    }

    static void print(int[] faces,int n){
        while(n>0){
            System.out.print(faces[n] + " ");
            n -= faces[n];
        }
        System.out.println();
    }

    //记忆化搜索（自顶向下的调用）,使用数组dp进行记忆
    static int coins2(int n){
        if(n<1) return Integer.MAX_VALUE;
        //第0个空间不用，使用从第一个到第n个索引
        int[] dp = new int[n+1];  //存放递归查找过的结果
        int[] faces = {1,5,20,25}; //面值数组
        for (int face : faces) { //只要面值小于n,说明该面值是存在的，可以直接得出结论
            if(n<face) break; //硬币已经存在
            dp[face] = 1;
        }
        return coins2(n,dp);
    }

    static int coins2(int n,int[] dp){
        if(n<1) return Integer.MAX_VALUE;
        if(dp[n] == 0){ //还没有查找过
            int min1 = Math.min(coins2(n-25,dp),coins2(n-20,dp));
            int min2 = Math.min(coins2(n-5,dp),coins2(n-1,dp));
            dp[n] = Math.min(min1,min2) + 1;
        }
        return dp[n];
    }

    //暴力递归（自顶向下）,有重叠子问题
    //函数定义:凑到n分需要的最少硬币个数,
    static int coins(int n){
        if(n<1) return Integer.MAX_VALUE; //当出现了负数，返回最最大值
        //1.寻找递归基,硬币规模：1，5，20，25
        if(n == 25 || n == 20 || n == 5 || n == 1) return 1;

        int min1 = Math.min(coins(n-25),coins(n-20));
        int min2 = Math.min(coins(n-5),coins(n-1));

        return Math.min(min1,min2) + 1;
    }

}
